#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Software: PyCharm
# @Version : Python-
# @Author  : Shengji He
# @Email   : hsjbit@163.com
# @File    : SortArrayParity2.py
# @Time    : 2020/11/12 10:21
# @Description:
from typing import List


class Solution:
    def sortArrayByParityII(self, A: List[int]) -> List[int]:
        """
        Given an array Aof non-negative integers, half of the integers in A are odd, and half of the integers are even.

        Sort the array so that whenever A[i] is odd, i is odd; and whenever A[i] is even, i is even.
        
        You may return any answer array that satisfies this condition.

        Example 1:
            Input: [4,2,5,7]
            Output: [4,5,2,7]
            Explanation: [4,7,2,5], [2,5,4,7], [2,7,4,5] would also have been accepted.

        Note:
            - 2 <= A.length <= 20000
            - A.length % 2 == 0
            - 0 <= A[i] <= 1000

        :param A:
        :return:
        """
        pEven = 0
        pOdd = 1
        while pEven < len(A) and pOdd < len(A):
            if A[pEven] % 2 != 0 and A[pOdd] % 2 != 1:
                A[pEven], A[pOdd] = A[pOdd], A[pEven]
                pEven += 2
                pOdd += 2
            elif A[pEven] % 2 != 0:
                pOdd += 2
            else:
                pEven += 2
        return A


if __name__ == '__main__':
    S = Solution()
    A = [4,2,5,7]
    print(S.sortArrayByParityII(A))
    print('done')
